11
3.2. Procena razdaljine
nOvde je problem proceniti dužinu najkraćeg puta između dve adrese u mreži (nadalje, to će se odnositi na “tačnu razdaljinu”). Dva alternativna pristupa će biti razmatrana ovde:
a)Proračunavanje tačne razdaljine između svih parova adresa u mreži, i njihovo skladištenje u tabeli rastojanja za naredno korišćenje.
b)Proračunavanje tačne razdaljine između dve adrese svaki put kada je to potrebno.
n Prvi pristup nije realan za velike mreže, iz razloga što bi tada tabela rastojanja bila prevelika da bi bila postavljena u glavnu memoriju ( primetimo da N adresa generišu O(N2) parovnih rastojanja). Sa druge strane izračunavanje tačne razdaljine “po zahtevu” je nefunkcionalno zbog mnogo vremena potrošenog na računanje. Procena najkraće putanje je skupa jer dve tačke mogu biti dosta udaljene, i specifične potrebe moraju biti uračunate pri proceni, kao što su jednosmerne ulice i zastoji pri skretanju u levo.
n Kako bi dosledno omogućili kraće vreme izračunavanja, uzeli smo međupristup tako što smo podelili mrežu ulica na 502 zone veličine kvadratnog kilometra. Unutar svake zone, najvažnija raskrsnica je definisana kao “centar” zone. Tačne razdaljine su izračunate između svakog para centara, i postavljene su u tabelu rastojanja. Veličina tabele je oko 1MB, i može biti postavljena u glavnu memoriju